package com.itheima.Array.sort;

import java.util.Arrays;

/**
 * @Author: Ethan Yankang
 * @Program: code-random-recordings
 * @Date: 2024-08-19 15:33
 **/
public class BucketSort {

    public static void bucketSort(int[] nums) {
        int n = nums.length;
        int min = nums[0], max = nums[0];
        // 找出数组中的最大最小值
        for (int i = 1; i < n; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }

        int bucketCount = (max - min) / n + 1; // 桶的个数
        int[][] buckets = new int[bucketCount][n]; // 使用二维数组作为桶
        int[] bucketSizes = new int[bucketCount]; // 记录每个桶中元素的个数

        // 将数组中的元素放入对应的桶中
        for (int num : nums) {
            int bucketIndex = (num - min) / n;
            buckets[bucketIndex][bucketSizes[bucketIndex]++] = num;
        }

        // 对每个桶中的元素进行排序，并合并到原数组中
        int index = 0;
        for (int i = 0; i < bucketCount; i++) {
            if (bucketSizes[i] > 0) {
                // 对桶中的元素进行排序
                Arrays.sort(buckets[i], 0, bucketSizes[i]);
                // 将排序好的桶中元素复制到原数组中
                for (int j = 0; j < bucketSizes[i]; j++) {
                    nums[index++] = buckets[i][j];
                }
            }
        }
    }
}